#pragma once

#include <vector>
#include <queue>
#include <set>

using namespace std;

template<typename G>
vector<int> bfs(const G &graph, int f = 0)
{
  queue<int> boundary;
  vector<bool> visited(graph.countNodes(),false);

  vector<int> order;
  order.reserve(graph.countNodes());

  boundary.push(f);
  visited[f] = true;
 
  while (boundary.size()) {
    // visitar
    int v = boundary.front();

    order.push_back(v);

    boundary.pop();

    for (int a: graph.getAdjacentNodes(v)) {
      if (!visited[a]) { 
        visited[a] = true;
        boundary.push(a);
      }
    }
  }; 

  return order;       
}

template<typename G>
class ArticulationSearch
{
public:
  struct MST
  {
    MST(int size):
    incideIn(size),
    incideOut(size)
    {
    }

    vector<set<int>> incideIn;
    vector<set<int>> incideOut;
  };

private:
  const G &_graph;
  vector<bool> _visited;
  vector<int> _order;
  vector<int> _preNum;
  vector<int> _posOrder;
  vector<int> _lowest;
  MST _mst;
  int _pNum;

public:
  ArticulationSearch(const G &graph):
  _graph(graph),
  _visited(graph.countNodes(),false),
  _mst(graph.countNodes()),
  _lowest(graph.countNodes(),0),
  _preNum(graph.countNodes(),-1),
  _pNum(0)
  {
    _order.reserve(graph.countNodes());
    _posOrder.reserve(graph.countNodes());
  }

  MST& dfs(int node)
  {
    _visited[node] = true;

    _order.push_back(node);

    _preNum[node] = _pNum++;

    for (int a: _graph.getAdjacentNodes(node)) {
      if (!_visited[a]) {
        _mst.incideOut[node].insert(a);
        _mst.incideIn[a].insert(node);
        dfs(a);
      } 
    }

    _posOrder.push_back(node);
    
    return _mst;
  }

  vector<int> getArticulations(int root = 0)
  {
    dfs(root);

    vector<int> r;
    
    // faço o processo em pós-ordem
    for (int i: _posOrder) {
      // não faço verificação para nó raíz que só tem um vértice filho
      if (i == root && _mst.incideOut[i].size() == 1) {
        continue;
      }
    
      vector<int> adjacents = _graph.getAdjacentNodes(i);

      _lowest[i] = _preNum[i];

      // pra todo adjacente ao atual cuja aresta não está na árvore
      for (int j: adjacents) {
        if (_mst.incideIn[i].find(j) == _mst.incideIn[i].end() &&
            _mst.incideOut[i].find(j) == _mst.incideOut[i].end()) {
          _lowest[i] = min(_lowest[i],_preNum[j]);
        }
      }
 
      bool isArticulation = false;
 
      // pra todo vértice filho do vértice atual
      for (int j: _mst.incideOut[i]) {
        _lowest[i] = min(_lowest[i],_lowest[j]);

        // verifico se o valor de menor do filho é maior ou igual a ordem do vertice atual
        isArticulation |= (_lowest[j] >= _preNum[i]);

        // se já se sabe ser uma articulação, para por aí e adiciona no array de saída
        if (isArticulation) {
          r.push_back(i);
          break;
        }
      }
    }

    return r;
  }
};
